package pro.softzhang.algo.lc500;

import pro.softzhang.algo.common.TreeNode;

public class LC543_DiameterOfBinaryTree {
    public static void main(String[] args) {

    }

    static
    class Solution {
        int diameter = 0;
        public int diameterOfBinaryTree(TreeNode root) {
            depth(root);
            return diameter + 1;
        }

        private int depth(TreeNode node) {
            if (node == null) {
                return 0;
            }

            int leftDiameter = depth(node.left);
            int rightDiameter = depth(node.right);
            diameter = Math.max(diameter, leftDiameter + rightDiameter);
            return Math.max(leftDiameter, rightDiameter);
        }
    }
}
